package leetcode_day._2021._202104._2131;

import java.util.TreeSet;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/22 9:34
 * 矩阵区域不超过 k 的最大数值和
 * 算法：前缀和
 * 先求出矩阵的前缀和
 * 然后再枚举所有的矩阵，这里是枚举所有的点，O(n * n * m * m)
 * ----------------------------------------
 * 可以枚举三条边
 * 上下右三条边固定
 *
 */
public class _22_363 {

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length, ans = Integer.MIN_VALUE;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) dp[i][j] = matrix[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        }
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                for (int ii = i; ii <= m; ii++)
                    for (int jj = j; jj <= n; jj++) {
                        // 计算矩阵为左上角(i, j) 和 右下角(ii, jj) 中元素的值
                        int tmp = dp[ii][jj] - dp[ii][j - 1] - dp[i - 1][jj] + dp[i - 1][j - 1];
                        ans = tmp <= k ? Math.max(ans, tmp) : ans;
                    }
        return ans;
    }

    public int maxSumSubmatrix_perfect(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
        int ans = Integer.MIN_VALUE;
        for (int top = 1; top <= m; top++)
            for (int bot = top; bot <= m; bot++) {
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                for (int r = 1; r <= n; r++) {
                    int right = pre[bot][r] - pre[top - 1][r];
                    // 不大于 right - k 的最大整数
                    Integer left = ts.ceiling(right - k);
                    if (null != left) {
                        int cur = right - left;
                        ans = Math.max(ans, cur);
                    }
                    ts.add(right);
                }
            }
        return ans;
    }
}
